package com.pandy.leetcode;

import java.util.Map;

/**
 * @description: 二叉树递归套路练习
 * 判断是否是搜索二叉树
 *
 * https://leetcode.cn/problems/validate-binary-search-tree/description/
 * @author: panhong
 * @date: 2025/3/31
 */
public class Code005_BinaryTree_BST {

    public static boolean isBST(BinaryTreeNode head) {
        if(head == null) {
            return true;
        }

        Info info = process(head);
        return info.isBST;
    }

    static class Info {
        private boolean isBST;
        private int max;
        private int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }

        public boolean isBST() {
            return isBST;
        }
    }

    public static Info process(BinaryTreeNode x) {
        if(x == null) {
            return null;
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int max = x.value;
        int min = x.value;

        if(leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if(rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }

        boolean isBST = true;
        if(leftInfo != null) {
            if(!leftInfo.isBST || leftInfo.max >= x.value) {
                isBST = false;
            }

        }
        if(rightInfo != null) {
            if(!rightInfo.isBST || rightInfo.min <= x.value) {
                isBST = false;
            }
        }

        return new Info(isBST,max,min);
    }

    public static void main(String[] args) {
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);


        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(7);
        BinaryTreeNode n8 = new BinaryTreeNode(8);

        n5.left = n4;
        n5.right = n7;
        //n4.left = n2;
        //n4.right = n3;

        //n7.left = n8;

        System.out.println(isBST(n5));
    }
}
